# 直接插入排序法  简化版
# 不用新建列表

from utils.array_utils import check_all
from utils.random_list import sjlb


def insert(arr):
    for i in range(len(arr)):
        cur = arr[i]
        pre = i - 1
        while pre >= 0 and cur < arr[pre]:
            arr[pre + 1] = arr[pre]
            pre -= 1
        arr[pre + 1] = cur


def insert_02(l):
    # 插入排序再练习 2022-5-18
    count = 0
    length = len(l)
    for i in range(1, length):
        cur = l[i]
        pre = i - 1
        while pre >= 0 and cur < l[pre]:
            count += 1
            l[pre + 1] = l[pre]
            pre -= 1
        l[pre + 1] = cur
    return count


if __name__ == '__main__':
    l = [49, 10, 96, 78, 57, 33, 66, 21, 49, 10, 96, 78, 57, 33, 66, 21, 87, -5, 91, 2, -51, 22, -18, -84, 49, 56]
    # print(l)
    # print(insert_02(l))
    # print(l)

    print(check_all(insert_02, 1000))
